package kyssion.leetcode.num1_50;

import kyssion.leetcode.util.ShowUtil;

public class code31_下一个全排列 {
    public static void main(String[] args) {
        int[] nums = new int[]{
                1,3,2
        };
        new code31_下一个全排列().nextPermutation(nums);
        ShowUtil.showArr(nums);
    }

    /**
     * 下一个排列就方法就是寻在从后往前升序排列的终止位置然后,交换后面升序排列的中倒数第一个比这个数字大的,然后将后面的数字从小到大排列
     * 非递归写法
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        int index = nums.length - 2;
        int changeIndex = nums.length - 1;
        while (index >= 0) {
            if (nums[index] < nums[index + 1]) {
                for (int a = nums.length - 1; a > index; a--) {
                    if (nums[a] <= nums[index] && nums[a - 1] > nums[index]) {
                        changeIndex = a - 1;
                        break;
                    }
                }
                break;
            }
            index--;
        }
        int change;
        if(index!=-1) {
            change = nums[index];
            nums[index] = nums[changeIndex];
            nums[changeIndex] = change;
        }
        int center = (nums.length + index) / 2;
        int add = (nums.length + index) % 2 == 0 ? 0 : 1;
        for (int a = index + 1; a < center + add; a++) {
            change = nums[a];
            nums[a] = nums[center + center - a + add];
            nums[center + center - a + add] = change;
        }
    }
}
